package main

func searchMatrix(matrix [][]int, target int) bool {
	n := len(matrix[0])
	// find row
	rowIdx := findRow(matrix, target)
	if rowIdx < 0 {
		return false
	}
	if matrix[rowIdx][n-1] < target {
		return false
	}
	// find target in row
	j := find(matrix[rowIdx], target)
	return j >= 0
}

func findRow(matrix [][]int, target int) int {
	i := 0
	j := len(matrix) - 1
	for i <= j {
		mid := (i + j) / 2
		if matrix[mid][0] <= target {
			i = mid + 1
		} else if matrix[mid][0] > target {
			j = mid - 1
		}
	}
	if j < 0 || j >= len(matrix) {
		return -1
	}
	return j
}

func find(row []int, target int) int {
	i := 0
	j := len(row) - 1
	for i <= j {
		mid := (i + j) / 2
		if row[mid] < target {
			i = mid + 1
		} else if row[mid] > target {
			j = mid - 1
		} else {
			return mid
		}
	}
	return -1
}

func main() {
	println(searchMatrix([][]int{
		{1},
	}, 1))
	println(searchMatrix([][]int{
		{1},
		{3},
	}, 3))
	println(searchMatrix([][]int{
		{1, 3, 5, 7},
		{10, 13, 16, 20},
		{23, 30, 34, 60},
	}, 13))
	println(searchMatrix([][]int{
		{1, 3, 5, 7},
		{13, 14, 16, 20},
		{23, 30, 34, 60},
	}, 13))
}
